package Test_1115;

import java.util.*;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */

//用栈实现队列
    //第一个用来入栈
    //第二个用来出栈
class MyQueue {
    public ArrayDeque<Integer> stack1;
    public ArrayDeque<Integer> stack2;
    public MyQueue() {
        stack1=new ArrayDeque<>();
        stack2=new ArrayDeque<>();
    }
    //把元素放在栈1中
    public void push(int x) {
          stack1.push(x);
    }

    public int pop() {
        if (empty()){
            return -1;
        }
        //如果栈2为空，将栈1所有元素放入zhan2
        if(stack2.isEmpty()){
             while(!stack1.isEmpty()){
                stack2.push(stack1.pop()); ;
             }
        }
        return stack2.pop();
    }

    public int peek() {
        if (empty()){
            return -1;
        }
        //如果栈2为空，将栈1所有元素放入zhan2
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop()); ;
            }
        }
        return stack2.peek();
    }

    public boolean empty() {
          return stack1.isEmpty()&& stack2.isEmpty();
    }
}
//用队列实现栈
class MyStack {
    public Queue<Integer> qu1;
    public Queue<Integer> qu2;
    public MyStack() {
        qu1=new LinkedList<>();
        qu2=new LinkedList<>();
    }
    //入栈
    public void push(int x) {
        if(!qu1.isEmpty()){
            qu1.offer(x);
        }else if(!qu2.isEmpty()){
            qu2.offer(x);
            //qu1和qu2都不为空
        }else {
            qu1.offer(x);
        }
    }
    //出栈
    public int pop() {
        if(empty()){
            return -1;
        }
        //如果qu1不为空，将qu1中size-1的元素，放到qu2中，返回qu1中最后的元素
        if(!qu1.isEmpty()){
            int size=qu1.size();
            for (int i = 0; i < size-1; i++) {
                qu2.offer(qu1.poll());
            }
            return qu1.poll();
        }else if(!qu2.isEmpty()){
            int size=qu2.size();
            for (int i = 0; i < size-1; i++) {
                qu1.offer(qu2.poll());
            }
        }
        return qu2.poll();
    }

    public int top() {
        if(empty()){
            return -1;
        }
        int val=0;
        //如果qu1不为空，将qu1中size-1的元素，放到qu2中，返回qu1中最后的元素
        if(!qu1.isEmpty()){
            int size=qu1.size();
            for (int i = 0; i < size; i++) {
                val=qu1.poll();
                qu2.offer(val);
            }
            return val;
        }else if(!qu2.isEmpty()){
            int size=qu2.size();
            for (int i = 0; i < size-1; i++) {
                val=qu2.poll();
            }

        }
        return val;
    }
//qu1和qu2都为空
    public boolean empty() {
           return qu1.isEmpty()&&qu2.isEmpty();
    }
}
//循环队列
class MyCircularQueue {
    public int front;
    public int rear;
    public int[] elem;
    public MyCircularQueue(int k) {
          elem=new int[k];
    }
//入队列
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        elem[rear]=value;
        rear=(rear+1)% elem.length;
        return true;
    }
//出队列
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        //front往后走
        front=(front+1)% elem.length;
        return true;
    }
//得到对头元素
    public int Front() {
         if(isEmpty()){
             return -1;
         }
         return elem[front];
    }
//得到队尾元素
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        int index=(rear==0)?elem.length-1:rear-1;
        return elem[index];
    }

    public boolean isEmpty() {
           return rear==front;
    }

    public boolean isFull() {
         return (rear+1)% elem.length== front;
    }
}
public class Test {
}
